import java.util.*;

/**
 * 349. 两个数组的交集
 * https://leetcode-cn.com/problems/intersection-of-two-arrays/
 */
public class Solutions_349 {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 2, 1}, nums2 = {2, 2};  // output: {2}
//        int[] nums1 = {4, 9, 5}, nums2 = {9, 4, 9, 8, 4};  // output: {9, 4}

        int[] result = intersection(nums1, nums2);
        System.out.println(Arrays.toString(result));
    }

    public static int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        // 交集的个数，取决于最短长度的数组
        int[] res = new int[Math.min(nums1.length, nums2.length)];
        int idx = 0;
        for (int num : nums1) {
            set.add(num);
        }
        for (int num : nums2) {
            if (set.contains(num)) {
                res[idx] = num;
                idx++;
                // 移除
                set.remove(num);
            }
        }
        // 共有 k 个交集
        return Arrays.copyOf(res, idx);
    }
}
